package 动态规划.背包问题;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author: yangwk
 * @date: 2023/3/28
 * @description:
 **/
public class 背包问题 {
    static boolean[] visited = new boolean[100];

    //给定一个数组nums,将元素分为若干个组，使得每组和相等，求出满足条件的所有分组中，
    // 组内元素和的最小值 第一行输入 m 接着输入m个数，表示此数组 数据范围:1<=M<=50,
    // 1<=nums[i]<=50
    public static void main(String[] args) {
        int[] arr = new int[]{3, 2, 1, 3};
        Arrays.sort(arr);

        group(arr);
    }

    public static void group1(int[] arr) {
        int length = arr.length;
        int sum = 0;
        for (int i : arr) {
            sum += i;
        }
        for (int i = length; i >= 1; i--) {
            int avg = sum / i;
            if (sum % i != 0) {
                continue;
            }
            int left = 0, right = 0;
            int des = 0;
            int depth = 0;
            List<List<Integer>> path = new ArrayList<>();
            while (left < arr.length && right < arr.length) {
                int ele = arr[right++];
                if (des + ele > avg) {
                    left++;
                    continue;
                }
                if (path.size() <= depth) {
                    List<Integer> newList = new ArrayList<>();
                    path.add(newList);
                }
                List<Integer> integers = path.get(depth);
                integers.add(ele);
                if (des + ele <= avg) {
                    des += ele;
                }
                if (des == avg) {
                    left = right;
                    depth++;
                    des = 0;
                }
            }
            System.out.println(path);
        }
    }

    public static void group(int[] arr) {
        int length = arr.length;
        int sum = 0;
        for (int i : arr) {
            sum += i;
        }
        for (int i = length; i >= 1; i--) {
            int avg = sum / i;
            if (sum % i != 0) {
                continue;
            }
            dfs1(arr, avg, 0, sum, new ArrayList<>(), 0, i);
        }
    }


    public static void dfs1(int[] arr, int sum, int curSum, int total, List<List<Integer>> path, int depth, int num) {
        if (total == 0 && depth == num) {
            System.out.println(path);
            return;
        }
        if (total == 0 && depth > num) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            if (visited[i]) {
                continue;
            }
            int ele = arr[i];
            curSum = curSum + ele;
            if (curSum > sum) {
                curSum -= ele;
                continue;
            }
            visited[i] = true;
            if (path.size() <= depth) {
                List<Integer> newList = new ArrayList<>();
                path.add(newList);
            }
            List<Integer> integers = path.get(depth);
            integers.add(ele);
            int originDepth = depth;
            if (curSum == sum) {
                curSum = 0;
                depth += 1;
            }
            dfs1(arr, sum, curSum, total - ele, path, depth, num);
            visited[i] = false;
            integers.remove(integers.size() - 1);
            curSum -= ele;
            depth = originDepth;
        }
    }

    public static void dfs(int[] arr, int start, int sum, int curSum, List<List<Integer>> path, int depth) {
        if (start == arr.length) {
            System.out.println(path);
            return;
        }
        int ele = arr[start];
        if (path.size() <= depth) {
            List<Integer> newList = new ArrayList<>();
            path.add(newList);
        }
        List<Integer> integers = path.get(depth);
        curSum = curSum + ele;
        if (curSum == sum) {
            curSum = 0;
            depth += 1;
        }
        if (curSum > sum) {
            curSum -= ele;
        }
        integers.add(ele);
        dfs(arr, start + 1, sum, curSum, path, depth);
    }
}
